Network systems and storage devices need to reliably handle and store data and, thus, typically implement some type of scheme for recovering data that has been lost, degraded or otherwise compromised. At the most basic level, one recovery scheme could simply involve creating one or more complete copies or mirrors of the data being transferred or stored. Although such a recovery scheme may be relatively fault tolerant, it is not very efficient with respect to the need to duplicate storage space. Other recovery schemes involve performing a parity check. Thus, for instance, in a storage system having stored data distributed across multiple disks, one disk may be used solely for storing parity bits. While this type of recovery scheme requires less storage space than a mirroring scheme, it is not as fault tolerant, since any two device failures would result in an inability to recover any compromised data.
Thus, various recovery schemes have been developed with the goal of increasing efficiency (in terms of the amount of extra data generated) and fault tolerance (i.e., the extent to which the scheme can recover compromised data). These recovery schemes generally involve the creation of erasure codes that are adapted to generate and embed data redundancies within original data packets, thereby encoding the data packets in a prescribed manner. If such data packets become compromised, as may result from a disk or sector failure, for instance, such redundancies could enable recovery of the compromised data, or at least portions thereof. Various types of erasure codes are known, such as Reed-Solomon codes, RAID variants, array codes (e.g., EVENODD, RDP, etc.) and XOR-based erasure codes which enable recovery of data due to disk or sector failures.
While implementation of an erasure code enables recovery of compromised data, the time required to reconstruct a failed disk also affects both the reliability and performance of the storage system. During the time that a failed disk is being recovered, the system may continue to operate in the foreground in a degraded performance mode in which reads to available disks to rebuild the failed disk are rate limited. Recovery may be performed serially, where each of the disks in the storage system is read in its entirety to recover the lost data, but such a technique is time-consuming. Alternatively, failed disks may be recovered in parallel, which reduces reconstruction time. The faster the failed disk can be reconstructed, the more reliable the storage system will be and the less time the system operates in a degraded performance mode. However, the price paid for a faster recovery typically is worse degraded mode performance as a result of the load that is placed on the system due to recovery efforts. To counteract degraded performance, scheduling reads from each available disk can be performed to reduce the load on any one disk. Thus, parallel recovery schemes may be implemented to reduce the load placed on each available disk and/or increase the rate at which the failed disk is recovered.